// https://www.lintcode.com/problem/longest-substring-with-at-most-k-distinct-characters/description

class Solution {
public:
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
        // set<char> rec; 需要记次数
        map<char, int> rec;
        int n = s.length();
        int res = 0;
        int cnt = 0;
        for (int l = 0, r = 0; r < n; ++r)
        {
            rec[s[r]]++;
            if (rec[s[r]] == 1)
                cnt++;
            while (cnt > k) //at most k
            {
                // l++; 无语了，要放后面
                rec[s[l]]--;
                if (rec[s[l]] == 0)
                    cnt--;
                l++;
            }
            if (r - l + 1 > res)
                res = r - l + 1;
        }
        return res;
    }
};